2020 Algorithm                     < No.5  Oil Search>                   Prof. Zoh Q.

2022 Algorithm                       < No.10 Slowdown>                 Prof. Zoh Q.

태업

slowdown strike라고 하는 것으로 일은 하되 의도적으로 천천히 일을 하여 작업의 능률을 떨어뜨리는 행위다. 우리나라에서 보통 “태업”이라고 부르는 사보타주(sabotage)는 이보다 훨씬 과격한 행동을 동반하는 것으로 기물을 훼손하는 폭력까지를 동반하는 파업을 의미한다.

[문제]   [eqn: k]대의 초정밀 측정기를 가진 연구기관이 있다. 이 업체는 연구자들의 의뢰를 받아서 특정 물질을 검사해준다. 검사에는 하루가 꼬박 걸린다. 이 업체는 미리 요청을 받은 작업을 바탕으로 1일부터 T일까지의 작업을 미리 확정하고자 한다. 작업(task) [eqn: t_i]의 요청은 처리해주면 지불할 비용 [eqn: c_i]와 원하는 마감 날짜(due date) [eqn: d_i]로 구성되어 있다. 작업을 처리해 줄 경우에는 반드시 마감일을 넘지 않아야 한다. 따라서 마감일 이전에 미리 작업을 처리하는 것은 가능하고, 처리할 수 없는 의뢰는 다시 돌려 보낸다.

그런데 연구기관에서는 연구원 대우 문제로 노동쟁의가 발생하였다. 이에 동조하는 연구원들은 작업에 최선을 다하지 않기로 하였다. 그러나 모든 작업을 거부할 수는 없으므로 얻을 수 있는 이익 중에서 최대가 아닌 차순위 단계의 이득을 받을 정도만 일을 하기로 하였다. 여러분은 주어진 N개의 작업을 [eqn: k]개의 기계로 처리할 때 얻을 수 있는 최대 이득(maximal profit)과 가능한 차순위의 최대 이득, 즉 2번째로 높은 이득(second maximal)을 계산해야 한다. 차순위 이득은 모든 실현 가능한 이득 중에서 최대 이득보다 작은(less than) 이득 중에서 최대인 것이다.

아래의 예를 들어 설명해보자. 만일 [eqn: T=5](일), [eqn: k=2](대)인 상황에서 아래와 같은 작업의뢰가 접수되었다고 하자. 그러면 욕심쟁이 방법으로 최대 이득을 확보할 수 있다. 그러나 최대 이득이 아닌 그 차순위 이득을 구하는 방법에 대해서는 조금 더 생각을 해야 한다.

[eqn: t_i]	1	2	3	4	5	6	7	8	9	10	11	12	13	14
[eqn: c_i]	32	25	55	60	27	44	15	40	33	28	51	24	33	28
[eqn: d_i]	4	3	2	3	2	5	5	4	1	2	4	4	3	1

maximal profit schedule (최대 이득 일정)

DAY	1	2	3	4	5
M1	t9	t3	t4	t11	t6
M2	t10	t1	t13	t8	t7

[입출력] 입력과 출력은 표준 입출력 stdio와 stdout을 사용한다. 입력 파일의 첫 줄에는 전체 작업의 개수 [eqn: | LEFT{ t_i RIGHT }|=N], 작업 일수 T, 기계의 대수 [eqn: k]를 나타내는 3개의 정수가 ‘[eqn: N~T ~ k]’로 주어진다. 이어지는 N개의 줄에는 각 작업의 이익과 마감 일자(due date)를 나타내는 숫자  ‘[eqn: c_i~ ~d_i]’가 주어진다. 여러분은 이 N개의 작업을 정리해서 얻을 수 있는 최대 이득 A와 차순위 (second maximal) 최대 이득  B를 두 개의 정수로 출력해야 한다. 즉 A > B 이며 이 사이의 값을 가지는 어떤 작업 일정도 있어서는 안된다. 입력 데이터의 범위는 다음과 같다.

[eqn: 3` LEQ `N` LEQ `100,] [eqn: 1 leq T leq 10, ~ 1 leq k leq 5],	[eqn: 1 LEQ c _{i} LEQ 100,] [eqn: ~1 LEQ d _{i} LEQ T]

stdio	stdout
14 5 2 32 4 25 3 55 2 ... 33 3 28 1	391 390

[제한조건] 프로그램 이름은 slow.{c, cpp, py}이다. 최대 수행시간은 1초이다.

2	-	7	*	1	-	6	+	5

	1	2	3	4	5
1	2	-5
2		7	7
3			1	-5
4				6	11
5					5

R[i:j]   R[1:5]